package fun.codedesign.jdk.math.algorithm.sort;

/**
 * 冒泡排序 <br>
 * 时间复杂度 O(n2)
 * 空间复杂度 O(1)
 *
 * @author zengjian
 * @create 2018-06-25 16:59
 * @since 1.0.0
 */
public class BubbleSorter implements Sorter {


    /**
     * 正序
     *
     * @param arr
     */
    @Override
    public void sort(int[] arr) {
        int size = arr.length - 1;
        // 外循环size次
        for (int i = 0; i < size; i++) {
            // 内循环=外循环次数-已占据次
            int count = size - i;
            // 从0开始冒泡，如果前一位比后一位大，则交换位置
            for (int j = i; j < count; j++) {
                if (arr[j] > arr[j + 1]) {
                    SorterUtils.swap(arr, j + 1, j);
                }
            }
        }
    }


    /**
     * 逆序
     *
     * @param arr
     */
    public void sortReverse(int[] arr) {
        int size = arr.length - 1;
        for (int i = 0; i < size; i++) {
            int count = size - i;
            for (int j = i; j < count; j++) {
                if (arr[j + 1] < arr[j]) {
                    SorterUtils.swap(arr, j + 1, j);
                }
            }
        }
    }
}